package com.xc.tree;

class BinarySearchTree {
    private TreeNode root;

    BinarySearchTree() {
        root = null;
    }

    public static void main(String[] args) {
        BinarySearchTree bst = new BinarySearchTree();
        bst.insert(50);
        bst.insert(30);
        bst.insert(20);
        bst.insert(40);
        bst.insert(70);
        bst.insert(60);
        bst.insert(80);
        System.out.println("Inorder traversal: "+bst);
    }

    // 插入节点
    void insert(int val) {
        root = insert(root, val);
    }

    private TreeNode insert(TreeNode node, int val) {
        if (node == null) {//第一个节点为null
            return new TreeNode(val);
        }

        if (val < node.val) {//val（30）比50（根节点），查到节点左边
            node.left = insert(node.left, val);
        } else if (val > node.val) {
            node.right = insert(node.right, val);
        }

        return node;
    }

}